//
//  grafo.h
//  sspayment_cliente_cpp
//
//  Created by Alexandre Albano on 03/07/12.
//  Copyright (c) 2012 Programa de Educação Tutorial PET/UFC Engenharia da Computação. All rights reserved.
//

#ifndef sspayment_cliente_cpp_grafo_h
#define sspayment_cliente_cpp_grafo_h

#define quantidade_vertices 6
#define quantidade_arcos 20
#define peso_max 99
#define quantidade_trocas (int)quantidade_vertices/2

#import "estrutura.h"

#include <iostream>

using namespace std;

class Grafo {
    lista_vertices G0[quantidade_vertices+1];
    lista_vertices G1[quantidade_vertices+1];
    int permutacao[quantidade_vertices+1];
    int permutacaoNova[quantidade_vertices+1];
    int composicao[quantidade_vertices+1];
    lista_vertices H[quantidade_vertices+1];
    lista_vertices H2[quantidade_vertices+1];

    
public:
    Grafo(){
        int origem, destino, peso;
        lista_sucessores *elemento_sucessor;
     
        //inicializa o vetor de vertices e aloca um sucessor 0 para cada
        for (int i=0; i<=quantidade_vertices; i++) {
            elemento_sucessor = new lista_sucessores();
            elemento_sucessor->cria_sucessor(0, 0);
            G0[i].cria_vertice(i, elemento_sucessor);
        }

        for (int i=0; i<quantidade_arcos; i++) {
            origem = (int)rand() % quantidade_vertices+1;
            destino = (int)rand() % quantidade_vertices+1;
            peso = (int)rand() % peso_max;
            elemento_sucessor = new lista_sucessores();
            elemento_sucessor->cria_sucessor(destino, peso);
            G0[origem].ultimo_sucessor->proximo_sucessor=elemento_sucessor;
            G0[origem].ultimo_sucessor=elemento_sucessor;
        }
    }
    
    void cria_permutacao(){
        for (int i=0; i<=quantidade_vertices; i++) {
            permutacao[i]=i;
        }
        for (int i=0; i<=quantidade_trocas; i++) {
            int A, B, C;
            A=(int)rand() % quantidade_vertices+1;
            B=(int)rand() % quantidade_vertices+1;
            C=permutacao[A];
            permutacao[A]=permutacao[B];
            permutacao[B]=C;
        }
    }

    void cria_permutacaoNova(){
        for (int i=0; i<=quantidade_vertices; i++) {
            permutacaoNova[i]=i;
        }
        for (int i=0; i<=quantidade_vertices; i++) {
            int A, B, C;
            A=(int)rand() % quantidade_vertices+1;
            B=(int)rand() % quantidade_vertices+1;
            C=permutacaoNova[A];
            permutacaoNova[A]=permutacaoNova[B];
            permutacaoNova[B]=C;
        }
    }
    
    void cria_composicao(){
        for (int i=0; i<=quantidade_vertices; i++) {
            composicao[permutacao[i]]=permutacaoNova[i];
        }
    }
    
    void cria_G1(){
        lista_sucessores *elemento_sucessor, *percorre_sucessor;
        
        for (int i=0; i<=quantidade_vertices; i++) {
            elemento_sucessor = new lista_sucessores();
            elemento_sucessor->cria_sucessor(0, 0);
            G1[i].cria_vertice(i, elemento_sucessor);
        }
        for (int i=0; i<=quantidade_vertices; i++) {
            percorre_sucessor = G0[i].sucessor->proximo_sucessor;
            while(percorre_sucessor!=NULL){
                elemento_sucessor = new lista_sucessores();
                elemento_sucessor->cria_sucessor(permutacao[percorre_sucessor->vertice], percorre_sucessor->peso);
                G1[permutacao[G0[i].vertice]].ultimo_sucessor->proximo_sucessor=elemento_sucessor;
                G1[permutacao[G0[i].vertice]].ultimo_sucessor=elemento_sucessor;
                percorre_sucessor=percorre_sucessor->proximo_sucessor;
            }
        }
        
        
    }
    
//    void cria_G1(){
//        lista_sucessores *elemento_sucessor, *percorre_sucessor;
//        
//        for (int i=0; i<=quantidade_vertices; i++) {
//            elemento_sucessor = new lista_sucessores();
//            elemento_sucessor->cria_sucessor(0, 0);
//            G1[i].cria_vertice(permutacao[G0[i].vertice], elemento_sucessor);
//        }
//        for (int i=0; i<=quantidade_vertices; i++) {
//            percorre_sucessor = G0[i].sucessor->proximo_sucessor;
//            while(percorre_sucessor!=NULL){
//                elemento_sucessor = new lista_sucessores();
//                elemento_sucessor->cria_sucessor(permutacao[percorre_sucessor->vertice], percorre_sucessor->peso);
//                G1[G0[i].vertice].ultimo_sucessor->proximo_sucessor=elemento_sucessor;
//                G1[G0[i].vertice].ultimo_sucessor=elemento_sucessor;
//                percorre_sucessor=percorre_sucessor->proximo_sucessor;
//            }
//        }
//        
//        
//    }

    void cria_grafoPermutado(){
        lista_sucessores *elemento_sucessor, *percorre_sucessor;
        
        for (int i=0; i<=quantidade_vertices; i++) {
            elemento_sucessor = new lista_sucessores();
            elemento_sucessor->cria_sucessor(0, 0);
            H[i].cria_vertice(i, elemento_sucessor);
        }
        for (int i=0; i<=quantidade_vertices; i++) {
            percorre_sucessor = G0[i].sucessor->proximo_sucessor;
            while(percorre_sucessor!=NULL){
                elemento_sucessor = new lista_sucessores();
                elemento_sucessor->cria_sucessor(permutacaoNova[percorre_sucessor->vertice], percorre_sucessor->peso);
                H[permutacaoNova[G0[i].vertice]].ultimo_sucessor->proximo_sucessor=elemento_sucessor;
                H[permutacaoNova[G0[i].vertice]].ultimo_sucessor=elemento_sucessor;
                percorre_sucessor=percorre_sucessor->proximo_sucessor;
            }
        }
    }
    
    void cria_grafoIsomorfo0(){
        lista_sucessores *elemento_sucessor, *percorre_sucessor;
        
        for (int i=0; i<=quantidade_vertices; i++) {
            elemento_sucessor = new lista_sucessores();
            elemento_sucessor->cria_sucessor(0, 0);
            H2[i].cria_vertice(i, elemento_sucessor);
        }
        for (int i=0; i<=quantidade_vertices; i++) {
            percorre_sucessor = G0[i].sucessor->proximo_sucessor;
            while(percorre_sucessor!=NULL){
                elemento_sucessor = new lista_sucessores();
                elemento_sucessor->cria_sucessor(permutacaoNova[percorre_sucessor->vertice], percorre_sucessor->peso);
                H2[permutacaoNova[G0[i].vertice]].ultimo_sucessor->proximo_sucessor=elemento_sucessor;
                H2[permutacaoNova[G0[i].vertice]].ultimo_sucessor=elemento_sucessor;
                percorre_sucessor=percorre_sucessor->proximo_sucessor;
            }
        }
    }

    void cria_grafoIsomorfo1(){
        lista_sucessores *elemento_sucessor, *percorre_sucessor;
        
        for (int i=0; i<=quantidade_vertices; i++) {
            elemento_sucessor = new lista_sucessores();
            elemento_sucessor->cria_sucessor(0, 0);
            H2[i].cria_vertice(i, elemento_sucessor);
        }
        for (int i=0; i<=quantidade_vertices; i++) {
            percorre_sucessor = G1[i].sucessor->proximo_sucessor;
            while(percorre_sucessor!=NULL){
                elemento_sucessor = new lista_sucessores();
                elemento_sucessor->cria_sucessor(composicao[percorre_sucessor->vertice], percorre_sucessor->peso);
                H2[composicao[G1[i].vertice]].ultimo_sucessor->proximo_sucessor=elemento_sucessor;
                H2[composicao[G1[i].vertice]].ultimo_sucessor=elemento_sucessor;
                percorre_sucessor=percorre_sucessor->proximo_sucessor;
            }
        }
    }
    
    bool verifica_isomorfismo(bool b){
        lista_sucessores *percorre_H, *percorre_H2;

        if (b==1){
            cria_grafoIsomorfo1();
            for (int i=0; i<=quantidade_vertices; i++) {
                percorre_H = H[i].sucessor->proximo_sucessor;
                percorre_H2 = H2[i].sucessor->proximo_sucessor;
                while(percorre_H!=NULL && percorre_H2!=NULL){
                    if((percorre_H->vertice - percorre_H2->vertice) || (percorre_H->peso - percorre_H2->peso)) return 0;// grafo diferente
                    percorre_H=percorre_H->proximo_sucessor;
                    percorre_H2=percorre_H2->proximo_sucessor;
                }
            }
        } else if (b==0) {
            cria_grafoIsomorfo0();
            for (int i=0; i<=quantidade_vertices; i++) {
                percorre_H = H[i].sucessor->proximo_sucessor;
                percorre_H2 = H2[i].sucessor->proximo_sucessor;
                while(percorre_H!=NULL && percorre_H2!=NULL){
                    if((percorre_H->vertice - percorre_H2->vertice) || (percorre_H->peso - percorre_H2->peso)) return 0; //grafo diferente
                    percorre_H=percorre_H->proximo_sucessor;
                    percorre_H2=percorre_H2->proximo_sucessor;
                }
            }
        }
        return 1; //grafo igual
    }
    
    void bagunca_H(){
        H[1].sucessor->proximo_sucessor->vertice=0;
    }

    void exibe_permutacao(){
        cout << "\nPermutação\n";
        for (int i=1; i<=quantidade_vertices; i++) {
            cout << i << " -> " << permutacao[i] << "\n";
        }
    }

    void exibe_permutacaoNova(){
        cout << "\nPermutação Nova\n";
        for (int i=1; i<=quantidade_vertices; i++) {
            cout << i << " -> " << permutacaoNova[i] << "\n";
        }
    }

    void exibe_composicao(){
        cout << "\nComposição\n";
        for (int i=1; i<=quantidade_vertices; i++) {
            cout << i << " -> " << composicao[i] << "\n";
        }
    }

    void exibe_G0(){
        cout << "\nGrafo G0\n";
        for (int i=1; i<=quantidade_vertices; i++) {
            lista_sucessores *elemento_sucessor;
            cout << G0[i].vertice << " -> ";
            elemento_sucessor = G0[i].sucessor->proximo_sucessor;
            while(elemento_sucessor!=NULL){
                cout << elemento_sucessor->vertice << " ";
                elemento_sucessor=elemento_sucessor->proximo_sucessor;
            }
            cout << "\n";
        }
    }

    void exibe_G1(){
        cout << "\nGrafo G1\n";
        for (int i=1; i<=quantidade_vertices; i++) {
            lista_sucessores *elemento_sucessor;
            cout << G1[i].vertice << " -> ";
            elemento_sucessor = G1[i].sucessor->proximo_sucessor;
            while(elemento_sucessor!=NULL){
                cout << elemento_sucessor->vertice << " ";
                elemento_sucessor=elemento_sucessor->proximo_sucessor;
            }
            cout << "\n";
        }
    }
    
    void exibe_H(){
        cout << "\nGrafo H\n";
        for (int i=1; i<=quantidade_vertices; i++) {
            lista_sucessores *elemento_sucessor;
            cout << H[i].vertice << " -> ";
            elemento_sucessor = H[i].sucessor->proximo_sucessor;
            while(elemento_sucessor!=NULL){
                cout << elemento_sucessor->vertice << " ";
                elemento_sucessor=elemento_sucessor->proximo_sucessor;
            }
            cout << "\n";
        }
    }
    void exibe_H2(){
        cout << "\nGrafo H2\n";
        for (int i=1; i<=quantidade_vertices; i++) {
            lista_sucessores *elemento_sucessor;
            cout << H2[i].vertice << " -> ";
            elemento_sucessor = H2[i].sucessor->proximo_sucessor;
            while(elemento_sucessor!=NULL){
                cout << elemento_sucessor->vertice << " ";
                elemento_sucessor=elemento_sucessor->proximo_sucessor;
            }
            cout << "\n";
        }
    }
};

#endif
